This invention relates generally to relational databases, and more particularly to evaluating subqueries in the SQL language used by relational database management systems.
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data as described below and in the drawings hereto: Copyright(copyright) 1996, Microsoft Corporation, All Rights Reserved.
Under certain conditions, the SQL language allows the use of a basic block Select/from/Where relational expression, which is a table-valued, inside scalar expressions. Such a relational expression inside a scalar expression is called a subquery. The SQL2 standard specifies three basic forms of subqueries.
In a scalar-valued subquery, the result must be a table with at most one row and one column, whose value is used in the scalar expression. For example,
2 * (Select Avg(Salary) from Employees).
An existential subquery returns a boolean value based on whether the subquery returns any rows. For example,
Case When Exists(select * from shippers where shipperid=20) Then 1 Else 0 End.
The third form, the quantified comparison, also returns a boolean value, which is obtained by comparing a scalar value with a list of values returned by the subquery. For example,
Case When X less than  greater than ALL(Select Customerid from Customers) Then 1 Else 0 End.
Scalar expressions containing subqueries will often be used in larger relational expressions, and can use columns or variables from its environment. A use of such an xe2x80x9couterxe2x80x9d variable is called a correlation. For example, the following query uses a subquery to find customers who have placed an order:
Select * from Customers c
where Exists(Select * From Orders o where o.customerid=c.customerid).
Database engines typically separate a query executor (QE) component from an expression service component (ES). The QE deals with execution of the relational parts of queries, and it calls a simpler ES module that deals with evaluation of scalar expressions, as needed. For example, in applying a filter on a table, the QE would consider each row in turn, call the ES to evaluate the filter condition and, based on the scalar result, either discard the row or pass it to a consumer. Thus, even the most straightforward evaluation of subqueries requires the ES to call back into the QE to resolve the relational expression.
There is a potentially large amount of processor state associated with the QE, and requiring the ES to call back requires the use of conceptually separate instances of the QE that get activated in a recursive fashion. This requires setting up and removing a context for each instantiation of the QE. Since scalar expressions are usually called once per row to process the expression, this expensive recursive invocation will be done many times for large databases. Additionally, this approach to the processing of subqueries requires complex implementation for the database engine.
In some cases, the use of a subquery can be replaced by a relation join as observed by W. Kim in xe2x80x9cOn optimizing an SQL-like nested query,xe2x80x9d ACM Transactions on Database Systems, Vol. 7, No. 3, September 1982, pp. 443-469. Such a substitution removes the need for recursive calls between QE and SE, and allows the use of any join algorithm, for example a hash join, or merge join as discussed by G. Graefe in xe2x80x9cQuery evaluation techniques for large databases,xe2x80x9d ACM Computing Surveys, Vol. 25, No. 2, 1993, pp. 73-170. Additional cases of subqueries which can be removed in this fashion have been proposed by U. Dayal in xe2x80x9cOf nests and trees: A unified approach to processing queries that contain nested subqueries,xe2x80x9d Proceedings of the International Conference on Very Large Databases ""87, pp. 197-208, R. A. Ganski, and H. K. T. Wong in xe2x80x9cOptimization of nested SQL queries revisited,xe2x80x9d Proceedings of ACM SIGMOD ""87 Internaltional Conference on Management of Data, San Francisco, Calif., pp. 23-33, and M. Muralikrishna in xe2x80x9cImproved unnesting algorithms for join aggregate SQL queries,xe2x80x9d Proceedings of the International Conference of Very Large Databases ""92, pp. 91-102.
There is a need in the art for a relational database management system that utilizes subquery substitution for relational queries and extends the capabilities of the substitution structure.
The above-mentioned shortcomings, disadvantages and problems are addressed by the resent invention, which will be understood by reading and studying the following specification.
SQL subqueries are converted into equivalent expressions having a special relational operator. The special relational operator assumes properties based on the type of the expression containing the subquery. The context of the subquery is also factored into the special relational operation. The relational operator itself is optimized, when possible, into a standard join operation. The conversion process maintains a list of parameter dependencies within the query and the relational operator utilizes this list at execution time to decrease the amount of processing required to produce the query output.
The special relational operator and processing of the present invention enables more efficient query execution because the properties of the special relational operator optimize the execution flow, and omit both unnecessary and redundant processes. Furthermore, the absence of subqueries in the converted query permits the implementation of a less complex database execution engine.
The present invention describes systems, clients, servers, methods, and computer-readable media of varying scope. In addition to the aspects and advantages of the present invention described in this summary, further aspects and advantages of the invention will become apparent by reference to the drawings and by reading the detailed description that follows.